package tree;

import java.util.LinkedList;
import java.util.Queue;

//二叉树的每个结点
class Node {
    public String val;
    public Node left;
    public Node right;
    public Node(String val) {
        this.val = val;
        this.left = null;
        this.right = null;
    }
}
//根结点来表示树
class Tree {
    Node root = null;
}

public class Test1 {
    //创建一颗树
    public static Node creatTree() {
        //创建结点连接起来
        Node a = new Node("A");
        Node b = new Node("B");
        Node c = new Node("C");
        Node d = new Node("D");
        Node e = new Node("E");
        Node f = new Node("F");
        Node g = new Node("G");
        a.left = b;
        a.right = c;
        b.left = d;
        b.right = e;
        c.right = f;
        e.left = g;
        return a;
    }
    //先序遍历
    public static void preOrder(Node root) {
        if (root == null) {
            return;
        }
        System.out.print(root.val + " ");
        preOrder(root.left);
        preOrder(root.right);
    }
    //中序遍历
    public static void inOrder(Node root) {
        if (root == null) {
            return;
        }
        inOrder(root.left);
        System.out.print(root.val + " ");
        inOrder(root.right);
    }
    //后序遍历
    public static void postOrder(Node root) {
        if (root == null){
            return;
        }
        postOrder(root.left);
        postOrder(root.right);
        System.out.print(root.val + " ");
    }
    //层序遍历
    public static void levelOrder(Node root) {
        if(root == null){
            return;
        }
        //1.先准备一个队列
        Queue<Node> queue = new LinkedList<>();
        //2.然后先把 根结点入队列
        queue.offer(root);
        //3.再出队列 , 然后再把出队列的子树入队列 , 循环反复 ,直到队列为空为止
        while (!queue.isEmpty()){
            Node ret = queue.poll();
            System.out.print(ret.val + " ");
            if(ret.left != null){
                queue.offer(ret.left);
            }
            if (ret.right != null){
                queue.offer(ret.right);
            }
        }
    }
    //求树的结点个数
//    //一、可以遍历整个树每次遍历 size++ (不推荐)
//    //size 需要使用成员变量
//    public static int size = 0;
//    public static int size(Node root) {
//        if (root == null) {
//            return 0;
//        }
//        size++;
//        size(root.left);
//        size(root.right);
//        return size;
//    }

    //二、使用递归来解决
    //根结点个数 1 + 左树的结点个数 + 右树的结点个数
    public static int size(Node root) {
        if (root == null){
            return 0;
        }
        return 1 + size(root.left) + size(root.right);
    }

    //求二叉树的叶子结点
    //左树的叶子结点 + 又树的叶子结点
    public static int getLeafSize(Node root) {
        if (root == null){
            return 0;
        }
        if (root.left == null && root.right == null){
            return 1;
        }
        return getLeafSize(root.left) + getLeafSize(root.right);
    }

    //求二叉树第 k 层的结点个数
    //左树的 k - 1 层结点个数 + 右树的 k - 1 层结点个数
    //k == 1 则结点个数为 1
    public static int getKLevalNodeCount(Node root, int k){
        if (root == null || k < 1){
            return 0;
        }
        if (k == 1){
            return 1;
        }
        return getKLevalNodeCount(root.left,k - 1) + getKLevalNodeCount(root.right, k - 1);
    }
    public static void main(String[] args) {
        //直接创建一颗树
        Node root = creatTree();
        //preOrder(root);
        //inOrder(root);
        //postOrder(root);
        //levelOrder(root);
        //System.out.println(size(root));
        //System.out.println(getLeafSize(root));
        System.out.println(getKLevalNodeCount(root,4));
    }
}
